#include <iostream>
using namespace std;

typedef int ElemType;

// 链表的定义

struct LNode {
    ElemType data;  // 数据域
    LNode * next;   // 指针域
};

typedef LNode * LinkList;

// 链表初始化
bool InitList(LinkList &L)
{
    L = (LinkList) malloc(sizeof(LNode));       // 产生头结点，并使得L指向该节点
    if (!L)
        return false;
    L->next = NULL; // 头结点的指针域为空
    return true;
}

// 头插法创建链表
void CreateListHead(LinkList &L, int n)
{
    for (int i = 0; i < n; i++)
    {
        LNode *p = (LinkList) malloc(sizeof(LNode));
        cin >> p->data;
        // 这两句是关键
        p->next = L->next;      // 让新结点指向头结点的下一个结点
        L->next = p;            // 让头结点指向新结点
    }
}

// 尾插法创建链表
void CreateListTail(LinkList &L, int n)
{
    LNode *r = L;
    for (int i = 0; i < n; i++)
    {
        LNode *p = (LinkList) malloc(sizeof(LNode));
        cin >> p->data;

        p->next = r->next;
        r->next = p;
        r = r->next;

        // p->next = NULL;
        // r->next = p;
        // r = r->next;
    }
}

// 判断链表是否为空
bool IsEmpty(LinkList L)
{
    if (L->next != NULL)
        return false;
    else
        return true;
}

// 销毁链表
bool DestroyList(LinkList &L)
{
    LinkList q; // 暂时的
    while (L != NULL)
    {
        q = L->next;    // q指向首元结点
        free(L);        // 释放头结点
        L = q;          // L指向现头结点
    }
    
}

// 统计链表长度
int GetLength(LinkList L)
{
    int i = 0;  // 记初值为0
    LNode * p = L->next;   // p指向第一个节点
    
    while (p != NULL)
    {
        i++;
        p = p->next;
    }
    
    return i;
}

// 取链表中第i个元素的值
bool GetElem(LinkList L, int i, ElemType &e)
{
    if (i < 0)
    {
        cout << "out of range" << endl;
        return false;
    }
    LNode *p = L->next;     // 让 p 指向首元结点
    for (int j = 1; j < i; j++)
    {
        p = p->next;
        if (!p)
        {
            cout << "out of range" << endl;
            return false;
        }
    }
    e = p->data;
    return true;
}

// 按值查找链表
int LocateElem(LinkList &L, ElemType &e) 
{
    LNode *p = L->next;
    int cnt = 1;
    
    while (p)
    {
        if (p->data == e)
            return cnt;
        cnt++;
        p = p->next;
    }
    cout << "没发现" << endl;
    
    return 0;
}

// 在链表中插入元素
bool InsertList(LinkList &L, int i, ElemType &e)
{
    LNode *p = L;
    LNode *newNode;     // 新结点
    int j = 0;

    while (p && j < i - 1)    // 寻找第i-1个节点
    {
        j++;
        p = p->next;
    }
    if (!p || i < 0)
    { 
        cout << "out of range" << endl;
        return false;
    }
    newNode = (LinkList) malloc(sizeof(LNode));     
    newNode->data = e;
    // 这两句顺序不能变
    newNode->next = p->next;
    p->next = newNode;

    return true;
}

// 删除链表某个节点
bool DeleteList(LinkList &L, int i)
{
    LNode *p = L;
    int j = 0;

    while (p->next && j < i - 1)    // 寻找第i个结点，令p指向它的前驱
    {
        p = p->next;
        j++;
    }
    if (!(p->next) || i < 0)
    {
        cout << "out of range" << endl;
        return false;
    }
    LNode *q = p->next;     // q指向待删除结点
    p->next = p->next->next;    // 待删除结点的前驱指向待删除结点的后继
    free(q);    // 释放待删除结点

    return true;    
}
